package com.company.exp2.util;

import java.util.Comparator;

/**
 * @author dyy
 *
 * @param <T> 队列中的元素类型
 */
public class OrderedList<T>{
    class Node{
        T value;
        Node next;
        public Node(T value){
            this.value = value;
            this.next = null;
        }
        public Node(T value, Node node){
            this.value = value;
            this.next = node;
        }
    }

    Node frontPointer;
    Node backPointer;
    int size;

    public OrderedList(){
        frontPointer = null;
        backPointer = null;
        size = 0;
    }

    public boolean empty(){
        return size() == 0;
    }

    public int size(){
        return size;
    }

    public void pop(){
        assert size != 0 : "PopError : 队列为空";
        frontPointer = frontPointer.next;
        size--;
    }

    public void push(T element){
        if(size == 0){
            backPointer = new Node(element);
            frontPointer = backPointer;
        }else{
            backPointer.next = new Node(element);
            backPointer = backPointer.next;
        }
        size++;
    }

    public void orderedInsert(T element, Comparator<T> comparator) {
        if (size == 0) {
            push(element);
        } else {
            int index = 0;
            Node leftP = frontPointer;
            Node rightP = frontPointer;
            boolean hasInsert = false;
            while (rightP != null) {
                if (comparator.compare(rightP.value, element) > 0) {
                    if (index == 0) {
                        leftP = new Node(element, frontPointer);
                        frontPointer = leftP;
                    } else {
                        leftP.next = new Node(element, rightP);
                    }
                    hasInsert = true;
                    break;
                }
                if (index > 0) {
                    leftP = leftP.next;
                }
                rightP = rightP.next;
                index ++;
            }
            if (!hasInsert) {
                push(element);
            } else {
                size ++;
            }
        }
    }

    public T front(){
        assert size != 0 : "getError : 队列为空";
        return frontPointer.value;
    }

    public String toString() {
        StringBuilder result = new StringBuilder();
        Node p = frontPointer;
        while (p != null) {
            result.append(p.value.toString()).append(",");
            p = p.next;
        }
        return result.toString();
    }
}